package Z.dailyExercise.holiday;

import javax.swing.*;
import java.lang.reflect.MalformedParameterizedTypeException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class _面试题1005稀疏数组搜索 {
    /**
     *自解：难点：怎么在有一堆空字符中完成匹配
     * 暴力解 遍历数组 将非空的值存在map中 再对map进行二分查找
     * ---map不好二分查 所以用list存索引就行
     * ----复杂到不知道咋改了
     *
     */
    public int findString(String[] words, String s) {

        List<Integer> ls = new ArrayList<>();
        for(int i=0;i<words.length;i++){
            if (words[i].length()>0){
                //map.put(i,words[i]);
                ls.add(i);
            }
        }

        //首字母在两端之外的直接返回
        if (s.charAt(0) < words[ls.get(0)].charAt(0)  || s.charAt(0) > words[ls.get(ls.size()-1)].charAt(0)){
            return -1;
        }

        int low =0;
        int high = ls.size()-1;

        while (low<=high){

            int mid = low+(high-low)/2;

           if (s.charAt(0) < words[ls.get(mid)].charAt(0)){
                high= mid-1;

            }else if (s.charAt(0) > words[ls.get(mid)].charAt(0)){
                low = mid+1;
            }else {
               if ( words[ls.get(mid)].equals(s)){
                   return mid;
               }else{
                   //存在多个同字母开头
                   int temp = mid;


                   //向左扫描
                   while (mid-1>=low && s.charAt(0) == words[ls.get(mid-1)].charAt(0)){
                       if (words[ls.get(mid-1)].equals(s)){
                           return mid-1;
                       }else {
                           mid--;
                       }
                   }
                   //向右扫描
                   while (temp+1 <= high &&  s.charAt(0) == words[ls.get(temp+1)].charAt(0)){
                       if (words[ls.get(temp+1)].equals(s)){
                           return temp+1;
                       }else {
                           temp++;
                       }

                   }

                   return -1;
               }
           }
        }

        return -1;



    }
    /**
     * 题解：有空字符串 那就排除字符串
     *1。空在两头 ：那就在求mid之前首先缩界 保证low、 high均非空
     * 2。空在中间：如果是mid  那么就mid左移动 直到不为空
     */

    public int findString1(String[] words, String s){


        return helper(words,s,0,words.length-1);
    }

    public int helper(String[] words,String s,int low,int high){
        while (high > low && words[high].equals("")){
            high--;
        }
        while (high > low && words[low].equals("")){
            low++;
        }

        if (s.compareTo(words[low])<0 || s.compareTo(words[high])>0){
            return -1;

        }

        int mid = low+(high-low)/2;
        while (mid>low && words[mid].equals("")){
            mid--;
        }

        if (s.equals(words[mid])){
            return mid;
        }

        int com = s.compareTo(words[mid]);
        if (com>0){
            return helper(words,s,mid+1,high);
        }else if (com<0){
            return helper(words,s,low,mid-1);
        }

        return -1;



    }

}

